This disclosure relates generally to the field of image processing. More particularly, but not by way of limitation, it relates to a technique for detecting lines in an image. Existing techniques for line detection in images have both speed and accuracy problems. In the context of line detection, any non-collinear pixel is typically considered as noise data. Prior art line detection techniques, however, typically do not differentiate collinear edges from non-collinear edges, and introduce many spurious lines. FIG. 1 is an example image and FIG. 2 is an edge map that illustrates this difficulty, with a large number of edges detected (hi this example by a Canny edge detector). Analyzing all of the edges in FIG. 2 for lines, typically using Hough transforms, is expensive and subject to errors caused by the spurious lines.
Knowledge about the lines in an image is useful in many image analysis applications. Hough transforms (HT) are a classical tool in image processing to find lines. Hough transforms take an edge map of an image as input and perform a “voting” process using:ρ=x×cos θ+y×sin θ
where ρ is the perpendicular distance from the origin and θ is the angle with the normal. Collinear points (xi, yi) with i=1, . . . , N are transformed into N sinusoidal curvesρ=xi×cos θ+yi×sin θ
in the (ρ, θ) plane, which intersect in the point (ρ, θ). Hough transforms involve trigonometric operations on every edge pixel and every angle in the Hough space, are very CPU and memory demanding. If the image is texture rich, the true line detections are typically drowned inside the false detection pool, such as is illustrated by the lines of image 300 of FIG. 3.